#include "stdafx.h"
#include "Queue.h"
#include "Dqueue.h"

#pragma once

using namespace std; 

struct TreeNode
{
	int data;
	TreeNode * left;
	TreeNode * right;
};

TreeNode* CreateNewNode(int data)
{
	TreeNode *newNode = (TreeNode *)malloc(sizeof(TreeNode));
	if (!newNode)
	{
		cerr << "Malloc failed";
		return NULL;
	}

	newNode->data = data;
	newNode->left = NULL;
	newNode->right = NULL;

	return newNode;
}

TreeNode * Insert(TreeNode *root, int data)
{
	if (root == NULL)
	{
		return CreateNewNode(data);
	}

	if (data < root->data)
	{
		// left subtree
		root->left = Insert(root->left, data);
	}
	else if (data > root->data)
	{
		// right subtree
		root->right = Insert(root->right, data);
	}
	
	// else data already exists and no need to insert

	return root;
}

TreeNode * InsertIte(TreeNode *root, int data)
{
	TreeNode * newNode = CreateNewNode(data);
		
	// special case - insert at the root
	if (root == NULL)
	{
		return newNode;
	}

	TreeNode * current = root;

	while(current != NULL)
	{
		if (data < current->data)
		{
			// If left child is not present, insert node
			if (!current->left)
			{
				current->left = newNode;
				break;
			}

			// left subtree
			current = current->left;
		}
		else if (data > current->data)
		{
			if (!current->right)
			{
				current->right = newNode;
				break;
			}

			// right subtree
			current = current->right;
		}
		else
		{
			// data already exists, no need to insert
			break;
		}
	}

	return root;
}

TreeNode * Find(TreeNode * root, int data)
{
	if(root == NULL)
	{
		return NULL;
	}
	else if(data < root->data)
	{
		return Find(root->left, data);
	}
	else if(data > root->data)
	{
		return Find(root->right, data);
	}

	return root;
}

TreeNode * FindMin(TreeNode * root)
{
	if(root == NULL || root->left == NULL)
	{
		return root;
	}

	return FindMin(root->left);
}

TreeNode * Remove(TreeNode * root, int data)
{
	if(root == NULL)
	{
		return NULL;
	}
	else if(data < root->data)
	{
		root->left = Remove(root->left, data);
	}
	else if(data > root->data)
	{
		root->right = Remove(root->right, data);
	}
	else if(root->left != NULL && root->right != NULL)
	{
		TreeNode * min = FindMin(root->right);
		root->data = min->data;
		root->right = Remove(root->right, root->data);
	}
	else
	{
		TreeNode * parent = root;

		if(root->left == NULL)
		{
			root = root->right;
		}
		else if(root->right == NULL)
		{
			root = root->left;
		}

		free(parent);
	}

	return root;
}

void PrintTree(const TreeNode *root)
{
	if(root == NULL)
	{
		cout << "Null tree" << endl;
		return;
	}

	QueueNode * front = NULL, * rear = NULL;
	TreeNode newLine, space;
	const TreeNode * data;
	bool lineEnd = false;

	Enqueue(&front, &rear, root);
	Enqueue(&front, &rear, &newLine);

	while((data = (const TreeNode *)Dequeue(&front, &rear)) != NULL)
	{
		if(data == &newLine)
		{
			cout << endl;
			if(lineEnd)
			{
				break;
			}
			Enqueue(&front, &rear, &newLine);
			lineEnd = true;
		}
		else if(data == &space)
		{
			cout << "-";
			Enqueue(&front, &rear, &space);
			Enqueue(&front, &rear, &space);
		}
		else
		{
			cout << " " << data->data << " ";
			Enqueue(&front, &rear, (data->left == NULL) ? &space : data->left);
			Enqueue(&front, &rear, (data->right == NULL) ? &space : data->right);
			lineEnd = false;
		}
	}
}

// Print line by line
// Hint - need a queue to save child nodes and queue should allow to enter null, to indicate a new line

void PrintLines(TreeNode *root)
{
	Queue<TreeNode *> nodeQueue;
	TreeNode *current = root;
	int data;

	// if no tree, return 
	if(!root)
	{
		cout << "Null tree" << endl;
		exit(0); 
	}

	// Enqueue the root and start with dequeuing elements
	nodeQueue.Enqueue(root);
	nodeQueue.Enqueue(NULL);

	while(nodeQueue.Dequeue(&current))
	{
		// Print out the data
		if (current == NULL)
			cout << endl;
		else 
			cout << current->data << "\t";

		// enqueue the left and right children
		if (current->left)
			nodeQueue.Enqueue(current->left);
		if (current->right)
			nodeQueue.Enqueue(current->right);

		// Add null
		nodeQueue.Enqueue(NULL);
	}
}

void InorderTraversal(const TreeNode *root)
{
	if (root == NULL)
	{
		return;
	}

	InorderTraversal(root->left);
	cout << root->data << endl;
	InorderTraversal(root->right);
}

void PreorderTraversal(const TreeNode *root)
{
	if (root == NULL)
	{
		return;
	}

	cout << root->data << endl;
	PreorderTraversal(root->left);
	PreorderTraversal(root->right);
}

void PostorderTraversal(const TreeNode *root)
{
	if (root == NULL)
	{
		return;
	}

	PostorderTraversal(root->left);
	PostorderTraversal(root->right);
	cout << root->data << endl;
}

TreeNode* CreateBinaryTree(TreeNode *root)
{
	root = Insert(root, 4);
	root = InsertIte(root, 10);
	root = Insert(root, 1);
	root = InsertIte(root, 3);
	root = Insert(root, 27);
	root = Insert(root, 7);
	root = Insert(root, 17);
	root = Insert(root, 14);
	root = InsertIte(root, 110);
	root = Insert(root, 11);
	root = InsertIte(root, 13);
	root = Insert(root, 127);
	root = Insert(root, 71);
	root = Insert(root, 117);

	return root;
}

void UseBinaryTree()
{
	TreeNode *root = NULL;

	root = CreateBinaryTree(root);
	
	// Print binary tree line by line - best first search 
	PrintTree(root);

	// In-order traversal 
	cout << "Inorder traversal:" << endl;
	InorderTraversal(root);

	// pre-order traversal 
	//cout << "Preorder traversal:" << endl;
	//PreorderTraversal(root);

	// post-order traversal
	//cout << "Postorder traversal:" << endl;
	//PostorderTraversal(root);

	cout << "Find: " << Find(root, 17)->data << endl;
	cout << "FindMin: " << FindMin(root)->data << endl;

	Remove(root, 17);

	cout << "Find: " << Find(root, 17) << endl;
	cout << "FindMin: " << FindMin(root)->data << endl;

	// In-order traversal 
	cout << "Inorder traversal:" << endl;
	InorderTraversal(root);
}

